/*
https://leetcode-cn.com/problems/k-similar-strings/solution/xiang-si-du-wei-k-de-zi-fu-chuan-by-leetcode/
 */
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Solution854 {
    public int kSimilarity(String s1, String s2) {
        if (s1.equals(s2)){
            return 0;
        }
        Map<String,Integer> map=new HashMap<>();
        map.put(s1,0);
        Queue<String> queue=new LinkedList<>();
        queue.offer(s1);
        while (!queue.isEmpty()){
            String target=queue.poll();
            int t1=-1;
            for (int i=0;i<s1.length();i++){
                if (target.charAt(i)!=s2.charAt(i)){
                    t1=i;
                    break;
                }
            }
            for (int j=t1+1;j<s2.length();j++){
                if (target.charAt(j)==s2.charAt(t1)){
                    StringBuilder stringBuilder=new StringBuilder();
                    stringBuilder.append(target, 0, t1).append(target.charAt(j)).append(target, t1+1, j).append(target.charAt(t1)).append(target.substring(j+1));
                    String t=stringBuilder.toString();
                    if (t.equals(s2)){
                        return map.get(target)+1;
                    }
                    if (!map.containsKey(t)){
                        map.put(t,map.get(target)+1);
                        queue.offer(t);
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution854().kSimilarity("abc","bca"));
    }
}
